class Solution {
public:
    vector<int> father;
    int find(int i) {
        if (father[i] != i) father[i] = find(father[i]);
        return father[i];
    }

    void Union(int i, int j) {
        int x = find(i);
        int y = find(j);
        if(x == y) return;
        if(x < y){
            swap(x,y);
        }
        
        father[y] = x;
    }

    bool q(int i, int j) {
        return find(i) == find(j);
    }
    
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        father.resize(m*n+1);
        
        for(int i = 0;i <= m*n;i++){
            father[i] = i;
        }
        
        for (int j = 0; j < n; j++) {
            if (grid[0][j]) Union(j, m*n);
            if (grid[m-1][j]) Union((m-1)*n+j, m*n);
        }

        for (int i = 0; i < m; i++) {
            if (grid[i][0]) Union(i*n, m*n);
            if (grid[i][n-1]) Union(i*n+n-1, m*n);
        }

        
        
         int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
        
                if (grid[i][j] == 0) continue;
                for (int d = 0; d < 4; d++) {
                    int ii = i + dx[d];
                    int jj = j + dy[d];
                    if (ii < 0 || jj < 0 || ii >= m || jj >= n || grid[ii][jj] == 0) continue;
                    Union(ii*n+jj, i*n+j);
                }
            }
        }

    int cnt = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] && find(i*n+j) != m*n) cnt++;
            }
        }
        return cnt;
    }
};
